package main;

/**
 * @author zhx
 * @since 2020-07-05
 * 给你 root1 和 root2 这两棵二叉搜索树。
 * <p>
 * 请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序.
 * <p>
 * https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/
 */

import com.sun.media.sound.SoftMixingDataLine;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * <code>
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 * </code>
 */
public class LeetCode20 {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> tree1 = new ArrayList<>();
        List<Integer> tree2 = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        middleOrder(root1,tree1);
        middleOrder(root2,tree2);
        ans.addAll(tree1);
        ans.addAll(tree2);
        Collections.sort(ans);
        return ans;
    }

    void middleOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        middleOrder(root.left, list);
        list.add(root.val);
        middleOrder(root.right, list);

    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            this.val = x;
        }
    }

}
